//给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [4,2,7,1,3,6,9]
//输出：[4,7,2,9,6,3,1]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：root = [2,1,3]
//输出：[2,3,1]
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目范围在 [0, 100] 内 
// -100 <= Node.val <= 100 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1230 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class InvertBinaryTree {
    public static void main(String[] args) {
        Solution solution = new InvertBinaryTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 前序和后序的递归遍历
         *
         * @param root
         * @return
         */
        /*
        public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }

            wrapNode(root);
            // 递归遍历(前序和后序都可以)
            invertTree(root.left);
            invertTree(root.right);

            return root;
        }

        public void wrapNode(TreeNode root) {
            TreeNode tempNode = root.left;
            root.left = root.right;
            root.right = tempNode;
        }
         */

        /**
         * 层序遍历
         *
         * @param root
         * @return
         */
        /*
        public TreeNode invertTree(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();

            if (root == null) {
                return null;
            }

            queue.offer(root);

            while (!queue.isEmpty()) {
                int len = queue.size();

                while (len > 0) {
                    TreeNode node = queue.poll();
                    wrapNode(node);
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                    len--;
                }
            }
            return root;
        }
        */

        /**
         * 统一迭代的中序遍历
         *
         * @param root
         * @return
         */
//        public TreeNode invertTree(TreeNode root) {
//            Stack<TreeNode> stack = new Stack<>();
//
//            if (root == null) {
//                return null;
//            }
//
//            stack.push(root);
//
//            while (!stack.isEmpty()) {
//                TreeNode node = stack.peek();
//                if (node != null) {
//                    stack.pop();    // 先出栈，防止重复
//                    if (node.right != null) stack.push(node.right);
//                    stack.push(node);
//                    stack.push(null);
//                    if (node.left != null) stack.push(node.left);
//                } else {
//                    stack.pop();    // 将null出栈
//                    node = stack.peek();
//                    stack.pop();
//                    wrapNode(node);
//                }
//            }
//            return root;
//        }

        /**
         * 中序递归法（不完全是中序）
         *
         * @param root
         * @return
         */
        /*public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }

            invertTree(root.left);  // 左
            wrapNode(root);         // 中
            invertTree(root.left);  // 左，此时已经翻转，相当于现在左边是右孩子

            return root;
        }*/

        /**
         * 用于交换两个节点
         *
         * @param root
         */
        public void wrapNode(TreeNode root) {
            TreeNode tempNode = root.left;
            root.left = root.right;
            root.right = tempNode;
        }

        // 统一迭代法
        /*public TreeNode invertTree(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();

            if (root == null) {
                return null;
            }

            stack.push(root);

            while (!stack.isEmpty()) {
                if (stack.peek() != null) {
                    TreeNode cur = stack.pop();
                    if (cur.left != null) stack.push(cur.left);
                    if (cur.right != null) stack.push(cur.right);
                    stack.push(cur);
                    stack.push(null);
                } else {
                    stack.pop();
                    TreeNode node = stack.pop();
                    wrapNode(node);
                }
            }
            return root;
        }*/

        /*public TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return root;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int len = queue.size();
                while (len > 0) {
                    TreeNode node = queue.poll();
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                    wrapNode(node);
                    len--;
                }
            }
            return root;
        }*/

        // 分解的思路，前序也可以
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return root;
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
